Sau đây là một chứng minh rằng không tồn tại một hàm khả tính nào quyết định được liệu một chương trình cho trước có dừng trên một dữ liệu vào cho trước hay không. Nói cách khác, nếu định nghĩa hàm h(i, x) trả về 1 nếu chương trình thứ i dừng trên dữ liệu vào x và 0 nếu nó không dừng, thì h là không tính được. Ở đây chương trình thứ i là theo thứ tự của một cách liệt kê tất cả các chương trình của một mô hình tính toán Turing đầy đủ.

Ý tưởng chính ở đây là chứng minh mọi hàm khả tính đều khác với hàm h. Thật vậy, xem xét một hàm f bất kì. Định nghĩa hàm khả tính g như sau:g(i) không được định nghĩa khi f(i,i) = 0 (chẳng hạn bằng cách g lặp mãi mãi khi f(i,i)=0)và bằng 0 trong trường hợp còn lại. Nhận thấy rằng nếu f khả tính thì g khả tính.

Do g khả tính, tồn tại một chương trình e trong mô hình tính toán đã định để tính hàm g. Theo định nghĩa của g, luôn xảy ra một trong hai trường hợp sau:

• g(e) = f(e, e) = 0. Khi đó h(e,e) = 1 vì chương trình e dừng trên dữ liệu e.
• g(e, e) ≠ 0. Trong trường hợp này h(e,e) = 0, do chương trình e không dừng trên dữ liệu vào e.

Trong cả hai trường hợp, f và h nhận giá trị khác nhau. Do f là một hàm khả tính bất kì, mọi hàm khả tính đều khác với h.